#include "mp5.h"
#include <stdlib.h>

/*
* Copyright vramesh2, jain10
*/

/*!
 * \file pqueue.h
 * \brief Definition for the pqueue class.
 * \author Vijay Ramesh
 *
 * This is a simple pqueue class.
 */

#ifndef _PQUEUE_H_
#define _PQUEUE_H_
#define TRUE 1
#define FALSE 0

#include <stdbool.h>
#include <unistd.h>

struct pqueue_t;
struct pqnode_t;

typedef int (*funcp)( void* , void* );
typedef struct pqnode_t pqnode_t;
typedef struct pqueue_t pqueue_t;

/*!
 * \brief A pqueue node struct.
 *
 * This is a simple pqueue node class with 2 pointers, next,value.
 * next points to the next node in the pqueue. value is a void pointer to the
 * address of the object being held in the pqueuenode.
 */
struct pqnode_t
{
   pqnode_t *next; /*!< next points to the next node in the pqueue. NULL if at the
                       end of the pqueue.*/
   pqnode_t *prev; /*!< prev points to the next node in the pqueue. NULL if at the
                       end of the pqueue.*/
   void *value;   /*!< value points to the structure held by the pqueue node.
                       NULL if empty.*/
};

/*!
 * \brief A pqueue struct.
 *
 * This is a simple pqueue struct with 2 pointers, front, back and two
 * helper variables, empty, and size. front points to the front of the pqueue.
 * back points to the back of the pqueue. empty is a bool, that is set to false
 * when the pqueue is not empty and true when the pqueue is empty. size is the
 * size of the pqueue.
 */
struct pqueue_t
{
   pqnode_t *front; /*!< front points to the qnode_t at the front of the pqueue.
                        NULL is the pqueue is empty.*/
   pqnode_t *back;  /*!< back poinsts to the qnode_t at the back of the pqueue.
                        NULL if pqueue is empty.*/
   bool empty;     /*!< empty is a boolean that is set to TRUE if the pqueue
                        contains no nodes, and is FALSE if the pqueue contains
                        nodes.*/
   int size;       /*!< size is always set to the size of the pqueue. 0 when
                        pqueue is empty.*/
   funcp less;  /*!< A function pointer which takes two pointers and
                        compares them. This function should return a - number if
                        the first param is greater than the second, 0 if they
                        are equal and a + number if first number if greater than
                        the second number.*/
};

/*!
 * \brief The initializer for the pqueue object.
 *
 * This sets all the pointers in the pqueue object to NULL, size to 0, and empty
 * to true.
 *
 * \param pqueue is the pqueue_t pointer.
 */
void pq_init ( pqueue_t *pqueue, funcp compare );

void pq_transfer ( pqueue_t *pqueueone, pqueue_t *pqueuetwo );
/*!
 * \brief An enqueue function
 *
 * This pushes a value to the back of the pqueue.
 *
 * \param pqueue is the pqueue_t pointer.
 * \param value is a pointer to the value to be pushed.
 * \return Returns an int, 0 on success and 1 on failure.
 */
int pq_enqueue ( pqueue_t *pqueue, void *value );

/*!
 * \brief A dequeue function
 *
 * This pops the value at the front of the pqueue.
 *
 * \param pqueue is the pqueue_t pointer.
 * \param value is a pointer to the value to be pushed.
 * \return Returns A pointer to the value at the front of the pqueue.
 */
void * pq_dequeue ( pqueue_t *pqueue );

/*!
 * \brief A destroy function
 *
 * This deletes all the space held by pqueue. The values held by each pqueuenode are
 * not deleted.
 *
 * \param pqueue is the pqueue_t pointer.
 */
void pq_destroy ( pqueue_t *pqueue );

/*!
 * \brief A set empty function
 *
 * This sets the empty variable in the pqueue_t by determinig is the pqueue is
 * empty. This is mainly an internal function and never needs to be called upon,
 * although you can call it if you feel like it.
 *
 * \param pqueue is the pqueue_t pointer.
 */
void pq_set_empty ( pqueue_t *pqueue );
#endif

pqueue_t sched_queue;
bool init = TRUE;
int last_job_fin_time = 0;
int total_jobs = 0;;
int total_response_time = 0;
int total_wait_time = 0;
int total_run_time = 0;
int call = 0;

typedef struct job
{
   int num;
   int time;
   int time_left;
   int start_wait_time;
   int prev_start_time;
   int running_time;
   int priority;
} job;

job *curr_job = NULL;

void show_queue() {
   if ( curr_job == NULL )
   {
      printf ( "\n" );
      return;
   }
   else
   {
      pqnode_t *temp_node;
      temp_node = sched_queue.front;
      int temp_int;
      printf ( "%d ", curr_job->num );
      while ( temp_node != NULL )
      {
         temp_int = *(int*) temp_node->value;
         printf ( "%d ", temp_int );
         temp_node = temp_node->next;
      }
      printf ( "\n" );
   }
}

int fcfs ( void *one, void *two )
{
   return 0;
}

int sjf ( void *one, void *two )
{
   job *jobone = (job*) one;
   job *jobtwo = (job*) two;
   if ( jobone->time_left < jobtwo->time_left )
   {
      return 1;
   }
   else if ( jobone->time_left > jobtwo->time_left )
   {
      return -1;
   }
   else
   {
      return 0;
   }
}

int pri ( void *one, void *two )
{
   job *jobone = (job*) one;
   job *jobtwo = (job*) two;
   if ( jobone->priority < jobtwo->priority )
   {
      return 1;
   }
   else if ( jobone->priority > jobtwo->priority )
   {
      return -1;
   }
   else
   {
      return 0;
   }
}

int rr ( void *one, void *two )
{
   return 0;
}

int new_job(int jobnum, int time, int running_time, int priority) {

    job *newjob = (job*) malloc ( sizeof ( job ));
    newjob->num = jobnum;
    newjob->time = time;
    newjob->start_wait_time = time;
    newjob->prev_start_time = -1;
    newjob->running_time = running_time;
    newjob->time_left = running_time;
    newjob->priority = priority;

    if ( init == TRUE )
    {
       if ( scheme == FCFS )
       {
         pq_init ( &sched_queue, fcfs );
       }
       else if ( scheme == SJF )
       {
         pq_init ( &sched_queue, sjf );
       }
       else if ( scheme == PSJF )
       {
         pq_init ( &sched_queue, sjf );
       }
       else if ( scheme == PRI )
       {
         pq_init ( &sched_queue, pri );
       }
       else if ( scheme == PPRI )
       {
         pq_init ( &sched_queue, pri );
       }
       else /* scheme == RR */
       {
         pq_init ( &sched_queue, rr );
       }
       init = FALSE;
    }
    job * temp_job;
    if (( scheme == PSJF ) || ( scheme == PPRI ))
    {
       if ( curr_job != NULL )
       {
          int runned = time - curr_job->prev_start_time;
          curr_job->time_left = curr_job->time_left - runned;
          curr_job->start_wait_time = time;
          temp_job = curr_job;
          pq_enqueue ( &sched_queue, (void*) curr_job );
       }
    }
    pq_enqueue ( &sched_queue, (void*) newjob );
    total_jobs += 1;
    total_run_time += running_time;
    /* This function is called every time 
       a new job enters the queue. */

    if ( curr_job == NULL )
    {
       curr_job = (job*) pq_dequeue ( &sched_queue );
      /* Insert code below to decide which job to run next if there 
         is more than one active job. Call that job: current_job */
      if ( curr_job != NULL )
      {
         if (( temp_job != NULL ) && ( call == time ) && ( curr_job->num !=
                  temp_job->num ))
         {
            temp_job->prev_start_time = -1;
         }
         if ( curr_job->prev_start_time == -1 )
         {
            total_response_time += time - curr_job->time;
            total_wait_time += time - curr_job->start_wait_time;
         }
         else
         {
            if ( scheme == RR )
            {
               total_wait_time += time - curr_job->start_wait_time;
            }
         }
         curr_job->prev_start_time = time;
         call = time;
         return curr_job->num;
      }
      else
      {
      /* If the processor is idle, return -1 */
         call = time;
        return -1;
      }
    }
    else
    {
       if (( scheme == PSJF ) || ( scheme == PPRI ))
       {
          curr_job = (job*) pq_dequeue ( &sched_queue );

          if ( curr_job != NULL )
          {
             if (( temp_job != NULL ) && ( call == time ) && ( curr_job->num !=
                      temp_job->num ))
             {
                temp_job->prev_start_time = -1;
                if ( scheme == PSJF )
                {
                  total_response_time -= 1;
                }
             }
             if ( curr_job->prev_start_time == -1 )
             {
                total_wait_time += time - curr_job->start_wait_time;
                total_response_time += time - curr_job->time;
             }
             curr_job->prev_start_time = time;
               call = time;
             return curr_job->num;
          }
          else
          {
             /* If the processor is idle, return -1 */
               call = time;
             return -1;
          }
       }
       else
       {
          if (( temp_job != NULL ) && ( call == time ) && ( curr_job->num !=
                   temp_job->num ))
          {
             temp_job->prev_start_time = -1;
          }
          if ( curr_job->prev_start_time == -1 )
          {
             total_wait_time += time - curr_job->start_wait_time;
             total_response_time += time - curr_job->time;
          }
          curr_job->prev_start_time = time;
               call = time;
          return curr_job->num;
       }
    }
}

int job_finished(int jobnum, int time) {

    /* This function is called every time 
       the current job finishes. */
   last_job_fin_time = time;
    free ( curr_job );
    curr_job = (job*) pq_dequeue ( &sched_queue );

    if ( curr_job != NULL )
    {
    /* Insert code below to decide which job to run next if the
       processor is not idle. Call that job: current_job */
      if ( curr_job->prev_start_time == -1 )
      {
         total_wait_time += time - curr_job->start_wait_time;
         total_response_time += time - curr_job->time;
      }
      else
      {
         total_wait_time += time - curr_job->start_wait_time;
      }
      curr_job->prev_start_time = time;
               call = time;
      return curr_job->num;
    }
    else
    {
    /* If the processor is idle, return -1 */
               call = time;
      return -1;
    }
}

int quantum_expired(int time) {

    /* This function is called in a round-robin schedule
       every time the time quantum expires. */
   if ( last_job_fin_time == time )
   {
               call = time;
      return curr_job->num;
   }
   else
   {
    int runned = time - curr_job->prev_start_time;
    curr_job->time_left = curr_job->time_left - runned;
    curr_job->start_wait_time = time;
    pq_enqueue ( &sched_queue, (void*) curr_job );
    curr_job = (job*) pq_dequeue ( &sched_queue );

    if ( curr_job != NULL )
    {
    /* Insert code below to decide which job to run next if the
       processor is not idle. Call that job: current_job */
      if ( curr_job->prev_start_time == -1 )
      {
         total_wait_time += time - curr_job->start_wait_time;
         total_response_time += time - curr_job->time;
      }
      curr_job->prev_start_time = time;
               call = time;
      return curr_job->num;
    }
    else
    {
       /* If the processor is idle, return -1 */
               call = time;
       return -1;
    }
   }
}

float average_response_time() {
    // Implement this function.
    return ((float)total_response_time) / ((float)total_jobs);
}

float average_wait_time() {
    // Implement this function.
    return ((float)total_wait_time) / ((float)total_jobs);
}

float average_turnaround_time() {
    // Implement this function.
    return (((float)total_wait_time) + ((float)total_run_time)) / ((float)total_jobs);
}

/*!
 * \file pqueue.c
 * \brief Implementation for the pqueue class.
 * \author Vijay Ramesh
 *
 * This is a simple queue class.
 */

void pq_init ( pqueue_t *pqueue, funcp compare )
{
   pqueue->front = NULL;
   pqueue->back = NULL;
   pqueue->empty = TRUE;
   pqueue->size = 0;
   pqueue->less = compare;
   return;
}

void pq_transfer ( pqueue_t *pqueueone, pqueue_t *pqueuetwo )
{
   pqueueone->front = pqueuetwo->front;
   pqueuetwo->front = NULL;
   pqueueone->back = pqueuetwo->back;
   pqueuetwo->back= NULL;
   pqueueone->empty = pqueuetwo->empty;
   pqueuetwo->empty = TRUE;
   pqueueone->size = pqueuetwo->size;
   pqueuetwo->size = 0;
   return;
}
int pq_enqueue ( pqueue_t *pqueue, void *value )
{
   pqnode_t *temp_node;
   temp_node = ( pqnode_t *) malloc ( sizeof ( pqnode_t ));
   if ( temp_node == NULL )
   {
      /* Out of memory */
      return 1;
   }
   else
   {
      temp_node->value = value;
      if ( pqueue->empty )
      {
         /* queue is empty */
         temp_node->next = NULL;
         temp_node->prev = NULL;
         pqueue->back = temp_node;
         pqueue->front = temp_node;
         /* Sucess */
      }
      else
      {
         /* queue is not empty */
         if ( pqueue->less ( temp_node->value, pqueue->front->value ) > 0 )
         {
            /* inserting at front of queue */
            pqueue->front->prev = temp_node;
            temp_node->next = pqueue->front;
            temp_node->prev = NULL;
            pqueue->front = temp_node;
         }
         else
         {
            pqnode_t *temp = pqueue->back;
            int diff = pqueue->less ( temp_node->value, temp->value );
            while ( diff > 0 )
            {
               temp = temp->prev;
               diff = pqueue->less ( temp_node->value, temp->value );
            }
            if ( temp->next != NULL )
            {
               temp->next->prev = temp_node;
               temp_node->next = temp->next;
            }
            else
            {
               pqueue->back = temp_node;
            }
               temp_node->prev = temp;
               temp->next = temp_node;
         }
         /* Sucess */
      }
      pqueue->size++;
      pq_set_empty ( pqueue );
      return 0;
   }
}

void * pq_dequeue ( pqueue_t *pqueue )
{
   if ( pqueue->empty )
   {
      return NULL;
   }
   else
   {
      void *temp_ptr;
      temp_ptr = pqueue->front->value;
      pqnode_t *temp_node;
      temp_node = pqueue->front;
      pqueue->front = pqueue->front->next;
      if ( pqueue->front != NULL )
      {
         pqueue->front->prev = NULL;
      }
      pqueue->size--;
      pq_set_empty ( pqueue );
      free ( temp_node );
      return temp_ptr;
   }
}

void pq_destroy ( pqueue_t *pqueue )
{
   while ( !pqueue->empty )
   {
      pq_dequeue ( pqueue );
   }
   free ( pqueue );
   return;
}

void pq_set_empty ( pqueue_t *pqueue )
{
   if ( pqueue->front != NULL )
   {
      pqueue->empty = FALSE;
   }
   else
   {
      pqueue->empty = TRUE;
   }
   return;
}
